/**
 * @file   merge_sort.cpp
 * @author xingyifan <xingyifan@xingyifan-VirtualBox>
 * @date   Sat Sep 26 21:24:53 2020
 * 
 * @brief  here are  the functions of mergesort
 * 
 * 
 */

#include "Student.h"
#include <limits>

/**
 * @file   Student.cpp
 * @author xingyifan <xingyifan@xingyifan-VirtualBox>
 * @date   Sun Oct  4 14:17:30 2020
 * 
 * @brief  Mergesort function
 * 
 * 
 */

// Merge two array to one
int Merge(Student *A, int p, int q, int r) {
    int l1 = q - p + 1;
    int l2 = r - q;

    Student B[l1+1];
    Student C[l2+1];
    
    for (int i=0;i<l1;i++) {
	B[i] =  A[p+i];
    }

    for (int i=0;i<l2;i++) {
	C[i] = A[q+i+1];
    }

    int k = 0;
    int j = 0;
    const double M = 6;
    B[l1].set_GPA(6);
    C[l2].set_GPA(6);
    
    for (int i=0;i<(r-p+1);i++) {
	if (B[k].get_GPA() < C[j].get_GPA()) {
	    A[p+i] = B[k];
	    k++;
	} else {
	    A[p+i] = C[j];
	    j++;
	}
    }

    return 0;
}

//divide the array
int Merge_Sort(Student *A, int a, int b) {
    int p;
    
    if (b>a) {
	p = (a + b) / 2;
	Merge_Sort(A, a, p);
	Merge_Sort(A, p+1, b);
	Merge(A, a, p, b);
    }

    return 0;
}

//an input function
int Start_Merge(Student *A, int n) {
    Merge_Sort(A, 0, n-1);
    
    return 0;
}

/**
 * @file   Student.cpp
 * @author xingyifan <xingyifan@xingyifan-VirtualBox>
 * @date   Sun Oct  4 14:17:58 2020
 * 
 * @brief  Student function
 * 
 * 
 */

//init function
Student::Student() {
}

//input data
int Student::set(int _std_no, char _major, double _GPA) {
    std_no = _std_no;
    major = _major;
    GPA = _GPA;

    return 0;
}

//output data
int Student::output() {
    std::cout << std_no << " ";
    std::cout << major << " ";
    std::cout << GPA << "\t";
}

//get std_no
int Student::get_std_no() {
    return std_no;
}

//get major
char Student::get_major() {
    return major;
}

//get GPA
double Student::get_GPA() {
    return GPA;
}

//set GPA
int Student::set_GPA(double _GPA) {
    GPA = _GPA;

    return 0;
}

//end
Student::~Student() {
    
}

/**
 * @file   Student.cpp
 * @author xingyifan <xingyifan@xingyifan-VirtualBox>
 * @date   Sun Oct  4 14:39:46 2020
 * 
 * @brief  Two sort function
 * 
 * 
 */

//sort major
int sort_m(Student *A, int n) {
    Heap(A, n );
    Heap_Sort(A, n);
    
    return 0;
}

//sort GPA
int arrange(Student *A, int n) {
    Start_Merge(A, n);
    
    return 0;
}

/**
 * @file   Student.cpp
 * @author xingyifan <xingyifan@xingyifan-VirtualBox>
 * @date   Sun Oct  4 14:18:14 2020
 * 
 * @brief  Heapsort function
 * 
 * 
 */

//build max Heap
int Heap(Student *A, int n) {
    for (int i=PARENT(n-1);i>=0;i--) {
	shiftdown(A, n, i);
    }

    return 0;
}

//shiftdown
int shiftdown(Student *A, int n, int i) {
    int rc = RIGHTCHILD(i);
    int lc = LEFTCHILD(i);

    if (lc >= n) {
	return 0;
    }

    int child = lc;
    if (rc < n && A[rc].get_major() > A[lc].get_major()) {
	child = rc;
    }

    if (A[child].get_major() > A[i].get_major()) {
	Student temp = A[child];
	A[child] = A[i];
	A[i] = temp;
	shiftdown(A, n, child);
    }

    return 0;
}

//final sort
int Heap_Sort(Student *A, int n) {
    while (n>0) {
	Student temp = A[0];
	A[0] = A[n-1];
	A[n-1] = temp;
	n--;
	shiftdown(A, n, 0);
    }

    return 0;
}

//a function to output A
int printout(Student *A, int n) {
    for (int i=0;i<n;i++) {
	if (i%4==0) {
	    std::cout << std::endl;
	}
        A[i].output();
    }

    return 0;
}
